// Source:
// http://www.ocoudert.com/blog/2010/07/07/how-to-write-abstract-iterators-in-c/
// (by Olivier Coudert)
//

#include <iterator>
#include <typeinfo>
#include <vector>
#include <set>

template<typename E>
class ItrBase {
public:
    ItrBase() {}
    virtual ~ItrBase() {}
    virtual void  operator++() {}
    virtual E&    operator*() const { return E(); }
    virtual ItrBase* clone() const { return new ItrBase(*this); }
    // The == operator is non-virtual. It checks that the
    // derived objects have compatible types, then calls the
    // virtual comparison function equal.
    bool operator==(const ItrBase& o) const {
        return typeid(*this) == typeid(o) && equal(o);
    }
protected:
    virtual bool equal(const ItrBase& o) const { return true; }
};

template<typename E>
class Itr {
public:
    Itr() : itr_(0) {}
    ~Itr() { delete itr_; }
    Itr(const Itr& o) : itr_(o.itr_->clone()) {}
    Itr& operator=(const Itr& o) {
        if (itr_ != o.itr_) { delete itr_; itr_ = o.itr_->clone(); }
        return *this;
    }
    Itr&  operator++() { ++(*itr_); return *this; }
    E&    operator*() const { return *(*itr_); }
    bool  operator==(const Itr& o) const {
        return (itr_ == o.itr_) || (*itr_ == *o.itr_);
    }
    bool  operator!=(const Itr& o) const { return !(*this == o); }

protected:
    ItrBase<E>* itr_;
};

class E;

typedef std::vector<E> Container;

class ItrAll : public ItrBase<E> {
private:
    typedef ItrAll     _Self;
    typedef ItrBase<E> _Super;
public:
    ItrAll(Container& c) : _Super(), c_(c) {}
    virtual ~ItrAll() {}
    virtual void  operator++() { ++itr_; }
    virtual E&    operator*() const { return *itr_; }
    virtual ItrBase<E>* clone() const { return new _Self(*this); }
protected:
    virtual bool equal(const ItrBase<E>& o) const {
        // Casting is safe since types have been checked by _Super::operator==
        const _Self& o2 = static_cast<const _Self&>(o);
        return &c_ == &o2.c_ && itr_ == o2.itr_;
    }
protected:
    Container&          c_;
    Container::iterator itr_;
};

class ItrNoRepeat : public ItrAll {
private:
    typedef ItrNoRepeat _Self;
    typedef ItrAll      _Super;
public:
    ItrNoRepeat (Container& c) : _Super(c) {}
    virtual ~ItrNoRepeat () {}
    virtual void  operator++() {
        _Super::operator++(); // Go to the next element then
        // look for an element that has not been visited yet.
        for (; itr_ != c_.end(); _Super::operator++()) {
            E& e = _Super::operator*();
            if (visited_.find(e) == visited_.end()) {
                visited_.insert(e);
                return;
            }
        }
    }
    virtual E&    operator*() const { return _Super::operator*(); }
    virtual ItrBase<E>* clone() const { return new _Self(*this); }
protected:
    virtual bool equal(const ItrBase<E>& o) const { return _Super::equal(o); }
protected:
    std::set<E> visited_;
};

// Build the container s range w/ and w/o repetition
Itr<E> begin(Container& c, bool noRepeat = false)
{
    Itr<E> o;
    if (noRepeat) {
        o.itr_ = new ItrNoRepeat(c);
    } else {
        o.itr_ = new ItrAll(c);
    }
    o.itr_->itr_ = c.begin();
    return o;
}

Itr<E> end(Container& c, bool noRepeat = false)
{
    Itr<E> o;
    if (noRepeat) {
        o.itr_ = new ItrNoRepeat(c);
    } else {
        o.itr_ = new ItrAll(c);
    }
    o.itr_->itr_ = c.end();
    return o;
};


